package a09_贪心算法;

//贪心：
//每个站点有补充，到下一个站点也有消耗
//gas: 2 5 2   3 5
//cost:1 2 8   2 4
//diff:1 3 -6  1 1
//如果从0出发：1 + 3 + (-6)为负数了
public class a11_加油站 {
    public static void main(String[] args) {
        int[] gas = new int[]{2,5,2,3,5};
        int[] cost = new int[]{1,2,8,2,4};
        canCompleteCircuit(gas, cost);
    }
    //d1 d2 d3
    //如果d1+d2 < 0 并且 d3 > 0
    //注意：d1+d2+d3 >= 0
    //证明：d3+d1 > 0
    public static int canCompleteCircuit(int[] gas, int[] cost) {
        int currentSum = 0;
        int totalSum = 0;
        int startIdx = 0;
        for (int i = 0; i < gas.length; i++) {
            currentSum += gas[i] - cost[i];
            totalSum += gas[i] - cost[i];
            if(currentSum < 0){
                startIdx = i + 1;
                currentSum = 0;
            }
        }
        if(totalSum < 0){
            return -1;
        }else {
            return startIdx;
        }

    }
}
